/**
 * Project Name:JavaBaseReview
 * Package Name:com.xuwei.base.search
 * author:David
 * Date:2016年5月20日上午11:29:15
 * Copyright (c) 2016, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.search;

import org.junit.Test;

import com.xuwei.base.link.Iterator;
import com.xuwei.base.tree.BinTreeNode;

/**
 * @author David
 * @since 2016年5月20日 上午11:29:15
 * @version 
 * @since JDK 1.6
 */
public class SearchTest {
	
	@Test
	public void test01(){
		BinTreeNode root = createTree();
		
		BinSearchTree search = new BinSearchTree(root);
		System.out.println("==========中序遍历二叉查找树================");
		Iterator tree = search.inOrderTree();
		for(tree.first();!tree.isDone();){
			System.out.print(((BinTreeNode)(tree.currentItem())).getData());
			tree.next();
			if(!tree.isDone()){
				System.out.print(",");
			}
		}
		System.out.println("\nMax is :"+(search.max(root)).getData());
		System.out.println("Min is :"+(search.min(root)).getData());
		
		BinTreeNode searchedNode = search.search(2);
		System.out.println(searchedNode.getData());
		
		Object data = search.remove(7);
		Object data2 = search.remove(9);
		Object data3 = search.remove(20);
		System.out.println("del: "+data);
		
		Iterator tree2 = search.inOrderTree();
		for(tree2.first();!tree2.isDone();){
			System.out.print(((BinTreeNode)(tree2.currentItem())).getData());
			tree2.next();
			if(!tree2.isDone()){
				System.out.print(",");
			}
		}
		
	}
	
	@Test
	public void testAVLTree(){
//		BinSearchTree search = new AVLTree(createTree());
//		printTree(search.inOrderTree());
//		search.insert(9);
		Integer[] arr = {2,3,4,6,7,9,13,17,18,20};
		BinSearchTree tree = new AVLTree();
		for(Integer i:arr){
			tree.insert(i);
		}
		
		System.out.println();
		printTree(tree.inOrderTree());
		
		
	}

	private void printTree(Iterator tree2) {
		for(tree2.first();!tree2.isDone();){
			BinTreeNode item = (BinTreeNode)(tree2.currentItem());
			StringBuilder sb = new StringBuilder(String.valueOf(item.getData()));
			if(item.hasLChild()||item.hasRChild()){
				sb.append("(");
			}
			if(item.hasLChild()){
				sb.append(item.getLChild().getData());
			}
			if(item.hasLChild()||item.hasRChild()){
				sb.append(",");
			}
			if(item.hasRChild()){
				sb.append(item.getRChild().getData());
			}
			if(item.hasLChild()||item.hasRChild()){
				sb.append(")");
			}
			sb.append("[").append(item.getHeight()).append("]");
			System.out.print(sb.toString());
			tree2.next();
			if(!tree2.isDone()){
				System.out.print(", ");
			}
		}
	}
	
	private void printRBTree(Iterator tree2) {
		for(tree2.first();!tree2.isDone();){
			RBTreeNode item = (RBTreeNode) tree2.currentItem();
			StringBuilder sb = new StringBuilder(String.valueOf(item.getKey()));
			sb.append("(");
			sb.append(item.getlChild().getKey()==null?"NIL":item.getlChild().getKey());
			sb.append(",");
			sb.append(item.getrChild().getKey()==null?"NIL":item.getrChild().getKey());
			sb.append(")");
			sb.append("[").append(item.getHeight()).append("]").append(item.toString());
			System.out.print(sb.toString());
			tree2.next();
			if(!tree2.isDone()){
				System.out.print(", ");
			}
		}
	}
	
	

	private BinTreeNode createTree() {
		BinTreeNode root  = new BinTreeNode(15);
		Integer[] arr = {2,3,4,6,7,9,13,17,18,20};
		BinTreeNode node6 = new BinTreeNode(6);
		BinTreeNode node18 = new BinTreeNode(18);
		root.setLChild(node6);
		root.setRChild(node18);
		
		BinTreeNode node3 = new BinTreeNode(3);
		BinTreeNode node7 = new BinTreeNode(7);
		node6.setLChild(node3);
		node6.setRChild(node7);
		
		BinTreeNode node2 = new BinTreeNode(2);
		BinTreeNode node4 = new BinTreeNode(4);
		node3.setLChild(node2);
		node3.setRChild(node4);
		
		BinTreeNode node13 = new BinTreeNode(13);
		node7.setRChild(node13);
		
		BinTreeNode node17 = new BinTreeNode(17);
		BinTreeNode node20 = new BinTreeNode(20);
		node18.setLChild(node17);
		node18.setRChild(node20);
		return root;
	}
	
	@Test
	public void testRBTree(){
//		RBTreeNode root  = new RBTreeNode(11, RBTreeNode.BLACK);
//		Object[] arr = {1,2,5,7,8,14,15};
		Object[] arr = {1,2,5,7,8,14};
		/*RBTreeNode node1 = new RBTreeNode(1, RBTreeNode.BLACK);
		RBTreeNode node2 = new RBTreeNode(2, RBTreeNode.RED);
		RBTreeNode node5 = new RBTreeNode(5, RBTreeNode.RED);
		RBTreeNode node7 = new RBTreeNode(7, RBTreeNode.BLACK);
		RBTreeNode node8 = new RBTreeNode(8, RBTreeNode.RED);
		RBTreeNode node14 = new RBTreeNode(14, RBTreeNode.BLACK);
		RBTreeNode node15 = new RBTreeNode(15, RBTreeNode.RED);
		
		node2.setLChild(node1);node2.setRChild(node7);
		node7.setLChild(node5);node7.setRChild(node8);
		node14.setRChild(node15);
		root.setLChild(node2);root.setRChild(node14);
		RBTree tree = new RBTree(root);*/
		
		RBTree tree = new RBTree();
		for(Object obj:arr){
			tree.insert(obj);
		}
		
//		printRBTree(tree.inOrderTree());
//		tree.insert(4);
//		System.out.println("\n");
		printRBTree(tree.inOrderTree());
	}
	
	

}
